#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

/* 
 * 顺序队列
 */

/*

	队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，

	而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。

	进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
 */

struct queue
{
  int * queue;
  int front, rear, len;
  int max_size;
};

void again_malloc(struct queue * src)
{
  int * des;
  int i;

  des = realloc(src->queue, 2 * src->max_size * sizeof(int));
  if (des == NULL) {
    printf("realloc fail.\n");
    exit(1);
  }

  src->queue = des;

  if (src->rear != src->max_size -1) {
    for (i = 0; i <= src->max_size; i++)
      src->queue[i + src->max_size] = src->queue[i];
    
    src->rear += src->max_size;
  }

  src->max_size = 2 * src->max_size;
}

void init(struct queue * src, int ms)
{
  if (ms <= 0)
    exit(1);

  src->max_size = ms;
  src->queue = malloc (ms * sizeof(int));
  if (src->queue == NULL)
    exit(1);

  src->front = src->rear = 0;
}

void in(struct queue * src, int value)
{
  //if ((src->rear + 1) % src->max_size == src->front)
  //src->rear = (src->rear + 1) % src->max_size;

  if (src->rear == src->max_size) {
    printf("queue was bottom.\n");
    return ;
  }
  else {
    src->queue[src->rear] = value;
    src->rear++;
  }
}

int out(struct queue * src)
{
  int temp;

  if (src->front == src->rear) {
    printf("queueu was empty.\n");
    exit(1);
  }

  // src->front = (src->front + 1) % src->max_size;
  temp = src->queue[src->front];
  src->front++;
  if (src->front == src->rear)
    src->front = src->rear = 0;

  return temp;
  // return src->queue[src->front++];
}

int peek(struct queue * src)
{
  if (src->front == src->rear) {
    printf("queue was empty.\n");
    exit(1);
  }

  return src->queue[(src->front + 1) % src->max_size];
}

int empty(struct queue * src) 
{
  if (src->front == src->rear)
    return 1;
  else
    return 0;
}

void clear(struct queue * src)
{
  if (src->queue != NULL) {
    free(src->queue);
    src->queue = NULL;
    src->front = src->rear = 0;
    src->max_size = 0;
  }
}

void display(struct queue * src)
{
  int i;

  i = src->front;
  printf("queue element is :\n");

  /*  while ((i % (src->max_size)) != src->rear ) {
    printf(" i=%d: %d ", i, src->queue[i]);
    i++;
    }*/

  for (i = src->front; i <= src->rear-1; i++) 
    printf("%d ", src->queue[i]);

  printf("\n\n");
}

int main()
{
  struct queue queue;
  
  init(& queue, 10);
  in(& queue, 1);
  in(& queue, 2);
  in(& queue, 3);
  in(& queue, 4);
  in(& queue, 5);
  in(& queue, 6);
  in(& queue, 7);
  in(& queue, 8);
  in(& queue, 9);
  in(& queue, 10);
  in(& queue, 11);	// queue was bottom.
  display(& queue);	// 1 2 3 4 5 6 7 8 9 10
  
  out(& queue);		// del 1
  out(& queue);		// del 2
  out(& queue);		// del 3
  display(& queue);	// 4 5 6 7 8 9 10

  in(& queue, 77);	// queue was bottom. 因为不是循环队列，需全部出列后才能再次入列，以下增加所测。
  //  in(& queue, 8);
  //in(& queue, 9);
  //in(& queue, 10);
  display(& queue);	// 4 5 6 7 8 9 10
  

  /*
   * 2017/7/27 再次调试所加
   */
  out(& queue);		// del 4
  out(& queue);		// del 5
  out(& queue);		// del 6
  out(& queue);		// del 7
  out(& queue);		// del 8
  out(& queue);		// del 9
  out(& queue);		// del 10
  display(& queue);	// 空

  in(& queue, 11);
  in(& queue, 22);
  in(& queue, 23);
  in(& queue, 24);
  in(& queue, 25);
  in(& queue, 26);
  in(& queue, 27);
  in(& queue, 28);
  in(& queue, 29);
  in(& queue, 30);
  in(& queue, 31);	// queue was bottom.
  display(& queue); // 11 22 23 24 25 26 27 28 29 30
}
